package class_0915SkipList;

public class SkipList<V> {

    private static final int MAX_LEVEL = 16;//跳表允许的最大层数
    private static final double PROBABILITY = 0.5; // 定义概率常量
    private final Node<V> dummyHead = new Node<V>(Integer.MIN_VALUE, null, MAX_LEVEL);
    private final Node<V> dummyTail = new Node<V>(Integer.MAX_VALUE, null, 0);
    private int curLevel;
    private int size;//链表长度

    //等级节点的定义。
    public static class Node<V> {
        int key; //键
        V value; //值
        Node<V>[] forwards; //前向指针数组

        public Node(int key, V value, int level) {
            this.key = key;
            this.value = value;
            this.forwards = (Node<V>[]) new Node[level];//前向指针有多少个，或者该等级节点
        }
    }

    {
        for (int i = 0; i < MAX_LEVEL; i++) {
            dummyHead.forwards[i] = dummyTail;
        }
    }

    public SkipList() {
        curLevel = 1;//基础层数。
    }

    public Node<V> search(int key) {
        Node<V> cur = dummyHead; // 从头节点开始遍历

        // 从最高层开始逐层向下遍历---尽可能靠近，越近越好。
        for (int i = curLevel - 1; i >= 0; i--) {
            while (cur.forwards[i] != dummyTail && cur.forwards[i].key < key) {
                cur = cur.forwards[i]; // 在当前层前进---尽可能往右走
            }
        }

        // 回到第0层（原始层），找到目标节点
        cur = cur.forwards[0];

        // 如果目标节点存在且与目标key匹配，则返回该节点
        if (cur != dummyTail && cur.key == key) {
            return cur;
        } else {
            // 如果结果是哨兵节点dummyTail，或者cur.key != key，键为key的节点不存在。
            return null;
        }
    }

    private int randomLevel() {
        int level = 1;//基础层，每个等级节点都应该保证其至少有一层存储原始链表
        while (Math.random() < PROBABILITY && level < MAX_LEVEL) {
            //随机的生成更高层数
            level++;
        }
        return level;//返回
    }

    public void insert(int key, V value) {
        Node<V>[] update = new Node[curLevel];
        Node<V> cur = dummyHead;

        //依旧从最高层出发， 不过这里还要额外记录每层key关键字节点的前驱等级节点。
        for (int i = curLevel-1; i >= 0; i--) {
            while (cur.forwards[i] != dummyTail && cur.forwards[i].key < key) {
                cur = cur.forwards[i];
            }
            update[i] = cur;  // 记录该层当前节点的位置
        }
        //cur是第一层key关键字节点理论位置的的前驱节点
        //现在往后讨论
        cur = cur.forwards[0];
        if (cur != dummyTail && cur.key == key) {
            cur.value = value;
            return;
        }
        // 如果key不存在，进行插入操作
        // 生成新节点的随机层数
        int level = randomLevel();
        //创建新节点
        Node<V> newNode = new Node<>(key, value, level);

        // 插入新节点，更新每层的前驱指针
        // 插入新节点，更新前向指针
        for (int i = 0; i < level; i++) {
            if (i < curLevel) {
                newNode.forwards[i] = update[i].forwards[i];
                update[i].forwards[i] = newNode;
            } else {
                // 新增的层级部分
                dummyHead.forwards[i] = newNode;
                newNode.forwards[i] = dummyTail;
            }
        }
        if(level>curLevel) {
            curLevel = level;
        }
    }

    public void delete(int key) {
        Node<V> cur = dummyHead;
        Node<V>[] update = (Node<V>[]) new Node[curLevel];
        for (int i = curLevel - 1; i >= 0; i--) {
            while (cur.forwards[i] != dummyTail && cur.forwards[i].key < key) {
                cur = cur.forwards[i];
            }
            update[i] = cur;
        }
        cur = cur.forwards[0];
        if (cur != dummyTail && cur.key == key) {
            //节点存在
            for (int i = 0; i < cur.forwards.length; i++) {
                update[i].forwards[i] = cur.forwards[i];
            }
            while(curLevel>1 && dummyHead.forwards[curLevel-1]==dummyTail){
                curLevel--;
            }
        }
        //节点不存在，那就啥也不干。
    }
}